package com.dzu.easy;

import java.util.Arrays;

/**
 * @author ZhaoDong
 * @date 2022/9/8 10:27
 * @description 645. 错误的集合
 * 集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
 *
 * 给定一个数组 nums 代表了集合 S 发生错误后的结果。
 *
 * 请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,2,4]
 * 输出：[2,3]
 * 示例 2：
 *
 * 输入：nums = [1,1]
 * 输出：[1,2]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/set-mismatch
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Test645 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(findErrorNums(new int[]{3, 3, 1})));
    }

    /**
     * 数学
     * 我们还可以利用数值范围为 [1, n][1,n]，只有一个数重复和只有一个缺失的特性，进行「作差」求解。
     *
     * 令 [1, n][1,n] 的求和为 tottot，这部分可以使用「等差数列求和公式」直接得出：tot = \frac{n (1 + n)}{2}tot=
     * 2
     * n(1+n)
     * ​
     *   ；
     * 令数组 numsnums 的求和值为 sumsum，由循环累加可得；
     * 令数组 sumssums 去重求和值为 setset，由循环配合「哈希表/数组」累加可得。
     *
     * 作者：AC_OIer
     * 链接：https://leetcode.cn/problems/set-mismatch/solution/gong-shui-san-xie-yi-ti-san-jie-ji-shu-s-vnr9/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param nums
     * @return
     */
    public static int[] findErrorNums2(int[] nums) {
        int n = nums.length;
        int[] cnts = new int[n + 1];
        int tot = (1 + n) * n / 2;
        int sum = 0, set = 0;
        for (int x : nums) {
            sum += x;
            if (cnts[x] == 0) set += x;
            cnts[x] = 1;
        }
        return new int[]{sum - set, tot - set};
    }

    /**
     * 计数
     * 一个朴素的做法是，使用「哈希表」统计每个元素出现次数，然后在 [1, n][1,n] 查询每个元素的出现次数。
     *
     * 在「哈希表」中出现 22 次的为重复元素，未在「哈希表」中出现的元素为缺失元素。
     *
     * 由于这里数的范围确定为 [1, n][1,n]，我们可以使用数组来充当「哈希表」，以减少「哈希表」的哈希函数执行和冲突扩容的时间开销。
     *
     * 作者：AC_OIer
     * 链接：https://leetcode.cn/problems/set-mismatch/solution/gong-shui-san-xie-yi-ti-san-jie-ji-shu-s-vnr9/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param nums
     * @return
     */
    public static int[] findErrorNums(int[] nums) {

        int n = nums.length;
        int[] cnts = new int[n + 1];
        for (int x : nums) {
            cnts[x]++;
        }
        int[] ans = new int[2];
        for (int i = 1; i <= n; i++) {
            if (cnts[i] == 0) {
                ans[1] = i;
            }
            if (cnts[i] == 2) {
                ans[0] = i;
            }
        }
        return ans;

    }
}
